package com.链表2;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * 说明：
 *
 * 给定的 n 保证是有效的。
 *
 * 进阶：
 *
 * 你能尝试使用一趟扫描实现吗？
 */
public class 删除链表的倒数第N个节点 {
    static class Solution {
        /**
         * 正数的结点 = 总结点-N +１
         * @param head
         * @param n
         * @return
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            int size =  0;
            ListNode pre = head;
            while (pre != null){
                pre = pre.next;
                size ++;
            }
            if(size <= 1){
                return null;
            }
            n  = size - n + 1;
            ListNode pre2 = new ListNode(-1);
            pre2.next = head;
            ListNode pre3 = pre2;

            for(int i = 0;i<n-1;i++){
                pre3 = pre3.next;
            }
            pre3.next = pre3.next.next;

            return pre2.next;
        }

        /**
         * 我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。
         *
         * 设置虚拟节点 dummyHead 指向 head
         * 设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
         * 移动 q，直到 p 与 q 之间相隔的元素个数为 n
         * 同时移动 p 与 q，直到 q 指向的为 NULL
         * 将 p 的下一个节点指向下下个节点
         *
         * 作者：MisterBooo
         * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/dong-hua-tu-jie-leetcode-di-19-hao-wen-ti-shan-chu/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         * @param head
         * @param n
         * @return
         */
        public ListNode removeNthFromEnd2(ListNode head, int n) {
            ListNode pre = new ListNode(-1);
            pre.next = head;
            ListNode fast = pre,slow = pre;
            int index = 0;
            while (fast != null){
                if(index >= n+1){
                    slow = slow.next;

                }
                fast = fast.next;
                index ++ ;

            }
            slow.next = slow.next.next;
            return pre.next;
        }
    }

    public static void main(String[] args) {
        MyLinkedList link = new MyLinkedList(new int[]{1,2});
        Solution solution = new Solution();
        ListNode node = solution.removeNthFromEnd2(link.head.next,2);


    }

}
